6576. Дорога
В одной стране n дорог, пронумерованных от 1 до n. Инженер-строитель должен построить
дороги общего пользования, которые соединят все города вместе, то есть должна
существовать возможность путешествия из любого города в любой другой, возможно,
через несколько городов. Его команда обследовала несколько маршрутов (дорогу
между любыми двумя городами). Каждая дорога является двунаправленной. Инженер
может построить двунаправленную дорогу за определенную стоимость (чем короче
маршрут, тем дешевле дорога).
Инженер никогда не
планировал дорожную систему заранее. Он просто выбирает одну из дорог в
зависимости от своих предпочтений и строит ее, пока все города не будут
соединены.
Сейчас инженер хочет
построить дорогу между городами p и q. Под давлением правительства, чтобы
уменьшить расходы, он просит Вас написать программу, которая решит, должен ли
инженер строить эту дорогу или нет. Ваша программа должна вывести “YES”, если после строительства
эта дорога станет частью кратчайшей дорожной системы, соединяющей все города. В
противном случае ваша программа должна вывести “NO”.
Вход.
Первая строка содержит количество тестов t
(t ≤ 10).
Каждый тест начинается со
строки из 4 целых чисел n, m, p
и q. Здесь n (2 ≤ n ≤ 10000)
– количество городов, m (1 ≤ m ≤ 20000) – число дорог, p и q
(1 ≤ p ≤ n, 1 ≤ q ≤ n) задают
города, между которыми просят построить дорогу инженера.
Далее каждая из m строк содержит 3 числа u, v
и w (1 ≤ u ≤ n, 1 ≤ v ≤ n, 1 ≤ w ≤ 400000)
указывающие на существование двусторонней дороги длины w между u и v. Длина каждой дороги уникальна. Между
парой городов может существовать только одна дорога. Между любой парой городов
обязательно существует путь. Все числа целые.
Выход.
Для каждого теста вывести “YES” если постройка дороги (p, q) будет входить в кратчайшую дорожную систему. Иначе вывести “NO”.
Пример входа |
Пример выхода |
3 2 1 1 2 1 2 4 3 3 2 3 1 2 1 1 3 2 2 3 3 4 5 3 4 1 2 1 1 3 3 3 4 2 1 4 4 4 2 5 |
YES NO YES |
графы – алгоритм Крускала
Запустим алгоритм Крускала
на входном графе. Во множество s занесем
ребра графа, принадлежащие минимальному остову. Далее проверяем,
принадлежит ли заданное ребро (p, q) минимальному остову. Для этого следует проверить, лежит ли пара (p, q) или (q, p) во множестве s.
Пример
Графы, заданные
в примерах, имеют вид:
Реализация алгоритма
Объявим структуру ребра графа (пара вершин
и вес ребра). Объявим массив ребер e.
struct Edge
{
int u, v, dist;
};
vector<Edge> e;
Объявим
массив parent, используемый системой непересекающихся
множеств.
vector<int> parent;
Функция Repr
находит представителя множества, в котором находится вершина n.
int Repr(int n)
{
while(n != parent[n]) n = parent[n];
return n;
}
Функция Union объединяет
множества, содержащие элементы x и y.
int Union(int x, int y)
{
x = Repr(x); y = Repr(y);
if (x == y) return 0;
parent[y] = x;
return 1;
}
Функция lt является
компаратором для сортировки ребер.
int lt(Edge a, Edge b)
{
return (a.dist < b.dist);
}
Основная
часть программы. Обрабатываем несколько тестов.
scanf("%d", &tests);
while (tests--)
{
Читаем
входные данные. Инициализируем массив parent.
scanf("%d %d %d %d", &n, &m, &p,
&q);
parent.resize(n + 1);
for (i = 1; i
<= n; i++) parent[i] = i;
Читаем
ребра графа.
e.resize(m);
for (i = 0; i < m; i++)
scanf("%d %d %d", &e[i].u, &e[i].v,
&e[i].dist);
Сортируем
ребра по возрастанию весов.
sort(e.begin(), e.end(), lt);
При
обработке очередного теста обнуляем переменную flag. Она будет равна 1 или 0 в зависимости от того,
принадлежит ли ребро (p, q) минимальному остову.
flag = 0;
Запускаем
алгоритм Крускала построения минимального остова. Если ребро (e[i].u, e[i].v) будет включено в минимальный остов, то проверяем,
совпадает ли оно с ребром (p, q).
for (i = 0; i < m; i++)
if (Union(e[i].u, e[i].v))
Следует
проверить два равенства: (e[i].u, e[i].v) = (p, q) и (e[i].u, e[i].v) = (q, p).
if ((e[i].u == p
&& e[i].v == q) ||
(e[i].u == q && e[i].v == p))
{
Если ребро
(e[i].u,
e[i].v) совпадает с (p, q), то устанавливаем
flag = 1 и выходим из цикла.
flag = 1;
break;
}
В зависимости от значения flag выводим ответ.
if (flag)
puts("YES");
else
puts("NO");
}
Реализация алгоритма – set
Объявим структуру ребра графа (пара вершин
и вес ребра). Объявим массив ребер e.
struct Edge
{
int u, v, dist;
};
vector<Edge> e;
Объявим
массив parent, используемый системой непересекающихся
множеств.
vector<int> parent;
Во
множестве s будем сохранять ребра, принадлежащие
минимальному остову.
set<pair<int, int> > s;
Функция Repr
находит представителя множества, в котором находится вершина n.
int Repr(int n)
{
while(n != parent[n]) n = parent[n];
return n;
}
Функция Union объединяет
множества, содержащие элементы x и y.
int Union(int x, int y)
{
x = Repr(x); y = Repr(y);
if (x == y) return 0;
parent[y] = x;
return 1;
}
Функция lt является
компаратором для сортировки ребер.
int lt(Edge a, Edge b)
{
return (a.dist < b.dist);
}
Основная
часть программы. Обрабатываем несколько тестов.
scanf("%d", &tests);
while (tests--)
{
Читаем
входные данные. Инициализируем массив parent.
scanf("%d %d %d %d", &n, &m, &p,
&q);
parent.resize(n + 1);
for (i = 1; i
<= n; i++) parent[i] = i;
Читаем
ребра графа.
e.resize(m);
for (i = 0; i < m; i++)
scanf("%d %d %d", &e[i].u, &e[i].v,
&e[i].dist);
Сортируем
ребра по возрастанию весов.
sort(e.begin(), e.end(), lt);
При
обработке очередного теста очищаем множество s.
s.clear();
Запускаем
алгоритм Крускала построения минимального остова. Если ребро (e[i].u, e[i].v) будет включено в минимальный остов, то
добавляем его во множество s.
for (i = 0; i < m; i++)
if (Union(e[i].u, e[i].v))
s.insert(make_pair(e[i].u, e[i].v));
Проверяем, принадлежит ли заданное ребро (p, q) минимальному остову. Для этого следует проверить, лежит ли пара (p, q) или (q, p) во множестве s.
if ((s.find(make_pair(p, q)) != s.end()) ||
(s.find(make_pair(q,
p)) != s.end()))
puts("YES");
else
puts("NO");
}
Java реализация
import java.util.*;
class Edge
{
int u, v, dist;
Edge (int u, int v, int dist)
{
this.u = u;
this.v = v;
this.dist = dist;
}
};
class Pair
{
int u, v;
Pair (int u, int v)
{
this.u = u;
this.v = v;
}
};
public class Main
{
static int mas[];
static int size[];
static int Repr(int n)
{
if (n == mas[n]) return n;
return mas[n] = Repr(mas[n]);
}
static int Union(int x, int y)
{
x = Repr(x); y = Repr(y);
if(x == y) return 0;
if (size[x] < size[y])
{
int temp = x; x = y; y = temp;
}
mas[y] = x;
size[x] += size[y];
return 1;
}
public static class MyFun implements Comparator<Edge>
{
public int compare(Edge a, Edge b)
{
return a.dist - b.dist;
}
}
public static class PairFun implements Comparator<Pair>
{
public int compare(Pair a, Pair b)
{
if (a.u == b.u) return a.v - b.v;
return a.u - b.u;
}
}
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
int tests = con.nextInt();
while(tests-- > 0)
{
int n = con.nextInt();
int m = con.nextInt();
int p = con.nextInt();
int q = con.nextInt();
mas = new int[n+1];
size = new int[n+1];
for(int i = 1; i <= n; i++)
{
mas[i] = i;
size[i] = 1;
}
Vector<Edge> v = new Vector<Edge>();
for(int i = 0; i < m; i++)
{
int x = con.nextInt();
int y = con.nextInt();
int dist = con.nextInt();
v.add(new Edge(x,y,dist));
}
Collections.sort(v, new MyFun());
TreeSet<Pair> s = new TreeSet<Pair>(new
PairFun());
for(int i = 0; i < m; i++)
if (Union(v.get(i).u,v.get(i).v) == 1) s.add(new Pair(v.get(i).u,v.get(i).v));
if(s.contains(new Pair(p,q)) || s.contains(new Pair(q,p)))
System.out.println("YES");
else
System.out.println("NO");
}
con.close();
}
}